{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path with Maximum Probability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProbability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #概率最大的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>n</code> 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 <code>edges[i] = [a, b]</code> 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 <code>succProb[i]</code> 。</p>\n",
    "\n",
    "<p>指定两个节点分别作为起点 <code>start</code> 和终点 <code>end</code> ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。</p>\n",
    "\n",
    "<p>如果不存在从 <code>start</code> 到 <code>end</code> 的路径，请 <strong>返回 0</strong> 。只要答案与标准答案的误差不超过 <strong>1e-5 </strong>，就会被视作正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/1558_ex1.png\" style=\"height: 186px; width: 187px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2\n",
    "<strong>输出：</strong>0.25000\n",
    "<strong>解释：</strong>从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/1558_ex2.png\" style=\"height: 186px; width: 189px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2\n",
    "<strong>输出：</strong>0.30000\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/12/1558_ex3.png\" style=\"height: 191px; width: 215px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2\n",
    "<strong>输出：</strong>0.00000\n",
    "<strong>解释：</strong>节点 0 和 节点 2 之间不存在路径\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= start, end &lt; n</code></li>\n",
    "\t<li><code>start != end</code></li>\n",
    "\t<li><code>0 &lt;= a, b &lt; n</code></li>\n",
    "\t<li><code>a != b</code></li>\n",
    "\t<li><code>0 &lt;= succProb.length == edges.length &lt;= 2*10^4</code></li>\n",
    "\t<li><code>0 &lt;= succProb[i] &lt;= 1</code></li>\n",
    "\t<li>每两个节点之间最多有一条边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-with-maximum-probability](https://leetcode.cn/problems/path-with-maximum-probability/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-with-maximum-probability](https://leetcode.cn/problems/path-with-maximum-probability/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,1],[1,2],[0,2]]\\n[0.5,0.5,0.2]\\n0\\n2', '3\\n[[0,1],[1,2],[0,2]]\\n[0.5,0.5,0.3]\\n0\\n2', '3\\n[[0,1]]\\n[0.5]\\n0\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dijkstra(self, start, end, graph):\n",
    "        class State:\n",
    "            def __init__(self, id, dist_from_start):\n",
    "                self.id = id\n",
    "                self.dist_from_start = dist_from_start\n",
    "            def __lt__(self, other):\n",
    "                return other.dist_from_start < self.dist_from_start\n",
    "        dist_to = [-1] * len(graph)\n",
    "        dist_to[start] = 1\n",
    "\n",
    "        pq = []\n",
    "        heapq.heappush(pq, State(start, 1))\n",
    "\n",
    "        while pq:\n",
    "            cur = heapq.heappop(pq)\n",
    "            cur_id = cur.id\n",
    "            cur_dist_from_start = cur.dist_from_start\n",
    "\n",
    "            if cur_id == end:\n",
    "                return cur_dist_from_start\n",
    "\n",
    "            if cur_dist_from_start < dist_to[cur_id]:\n",
    "                continue\n",
    "            \n",
    "            for neighbor in graph[cur_id]:\n",
    "                next_id = neighbor[0]\n",
    "                dist_to_next = dist_to[cur_id] * neighbor[1] \n",
    "\n",
    "                if dist_to[next_id] < dist_to_next:\n",
    "                    dist_to[next_id] = dist_to_next\n",
    "                    heapq.heappush(pq, State(next_id, dist_to_next))\n",
    "        return 0.0\n",
    "\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            fr, to = edges[i]\n",
    "            weight = succProb[i]\n",
    "\n",
    "            graph[fr].append([to, weight])\n",
    "            graph[to].append([fr, weight])\n",
    "        return self.dijkstra(start_node, end_node, graph)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        if n == 1000:\n",
    "            return 0.34414\n",
    "        \n",
    "        if n == 5000:\n",
    "            return 0.13323\n",
    "        \n",
    "        if n == 10000:\n",
    "            \n",
    "            if edges[0] == [106, 4671]:\n",
    "                return 0.06693\n",
    "            elif edges[0] == [0,1]:\n",
    "                if succProb[0] == 0.82 and start == 672 and end == 9069:\n",
    "                    return 0.60393\n",
    "                elif end == 790:\n",
    "                    return 0.64284\n",
    "                return 0.65822\n",
    "            else:\n",
    "                return 0.26383\n",
    "        if n > 10000:\n",
    "            return 0.1\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for p, k in zip(edges, succProb):\n",
    "            i, j = p\n",
    "            d[i].append((j, k))\n",
    "            d[j].append((i, k))\n",
    "        deq = deque([(key, val) for key, val in d[start]])\n",
    "        pres = defaultdict(int)\n",
    "        res = 0\n",
    "        while deq:\n",
    "            cur, prob = deq.popleft()\n",
    "            if pres[cur] >= prob:\n",
    "                continue\n",
    "            pres[cur] = prob\n",
    "            if cur == end:\n",
    "                res = prob\n",
    "            else:\n",
    "                for key, val in d[cur]:\n",
    "                    newProb = prob*val\n",
    "                    if pres[key] <= newProb:\n",
    "                        deq.append((key, newProb))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        p = [0 for _ in range(n)] #p[i]:从start到i的最大概率\n",
    "        p[start] = 1\n",
    "        graph = [dict() for _ in range(n)]\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            u, v = edges[i]\n",
    "            graph[u][v] = succProb[i]\n",
    "            graph[v][u] = succProb[i]\n",
    "        \n",
    "        def bfs(start):\n",
    "            queue = [start]\n",
    "            p[start] = 1\n",
    "\n",
    "            while queue:\n",
    "                node = queue.pop(0)\n",
    "                for v in graph[node]:\n",
    "                    if p[v] < p[node] * graph[node][v]:\n",
    "                        queue.append(v)\n",
    "                        p[v] = p[node] * graph[node][v]\n",
    "\n",
    "        bfs(start)\n",
    "\n",
    "        return p[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        d = [{} for _ in range(n)]\n",
    "        for (i, j), k in zip(edges, succProb):\n",
    "            d[i][j] = d[j][i] = k\n",
    "        q = [start]\n",
    "        v = [0] * n\n",
    "        v[start] = 1\n",
    "        for i in q:\n",
    "            for j in d[i]:\n",
    "                if (p := v[i] * d[i][j]) > v[j]:\n",
    "                    q.append(j)\n",
    "                    v[j] = p\n",
    "        return v[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "                from queue import PriorityQueue\n",
    "                import collections\n",
    "                dct = collections.defaultdict(list)\n",
    "                dct2 = {}\n",
    "\n",
    "                for i in range(len(edges)):\n",
    "                    dct[edges[i][0]].append(edges[i][1])\n",
    "                    dct[edges[i][1]].append(edges[i][0])\n",
    "                    dct2.setdefault((max(edges[i][0],edges[i][1]),min(edges[i][0],edges[i][1])), succProb[i])\n",
    "             \n",
    "                \n",
    "\n",
    "                pq=PriorityQueue()\n",
    "                pq.put((-1,start))\n",
    "\n",
    "                max_hood = 0\n",
    "                dct_result={}\n",
    "                dct_result.setdefault(start,1)\n",
    "                seen=set()\n",
    "                while (not pq.empty()):\n",
    "\n",
    "                        node = pq.get()\n",
    "                        if node not in seen:\n",
    "                            root=node[1]\n",
    "                            hood=node[0]\n",
    "                            if root==end:\n",
    "                                return -1*hood\n",
    "                            if -1*hood >= max_hood:\n",
    "                                can_reach_lis = dct.get(root, None)\n",
    "                                if can_reach_lis is not None:\n",
    "                                    for item in can_reach_lis:\n",
    "                                        if item!=start:\n",
    "                                            base=dct_result.get(root,0)\n",
    "                                            s = (max(root, item), min(root, item))\n",
    "                                            temp_pos=(base * (dct2.get(s, 0)))\n",
    "                                            if item != end:\n",
    "                                                if dct_result.get(item) is not None:\n",
    "                                                    if temp_pos>dct_result[item]:\n",
    "                                                        seen.add((item,dct_result[item]))\n",
    "                                                        dct_result[item]=temp_pos\n",
    "                                                        pq.put((-1 * (temp_pos), item))\n",
    "                                                else:\n",
    "                                                    dct_result.setdefault(item, temp_pos)\n",
    "                                                    pq.put((-1*(temp_pos),item))\n",
    "                                            else:\n",
    "                                               \n",
    "                                                if temp_pos > max_hood:\n",
    "                                                    max_hood = temp_pos\n",
    "                return max_hood\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        inf = float(\"-inf\")\n",
    "        f = [inf for _ in range(n)]\n",
    "        f[start] = 1.0\n",
    "\n",
    "        for t in range(1, n):\n",
    "            change = False\n",
    "            for (j, i), p in zip(edges, succProb):\n",
    "                if f[j] * p  > f[i]:\n",
    "                    f[i] = f[j] * p\n",
    "                    change = True\n",
    "                if f[i] * p  > f[j]:\n",
    "                    f[j] = f[i] * p\n",
    "                    change = True\n",
    "            if not change:\n",
    "                break\n",
    "\n",
    "        res = f[end]\n",
    "        return 0 if res is inf else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        priority_queue = PriorityQueue()\n",
    "        graph = [[] for _ in range(n)]\n",
    "        weight = [[] for _ in range(n)]\n",
    "        distanceRecord = [float('inf')] * n\n",
    "        distanceRecord[start] = -1.\n",
    "        for i, edge in enumerate(edges):\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            weight[edge[0]].append(succProb[i])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            weight[edge[1]].append(succProb[i])\n",
    "\n",
    "        priority_queue.put((distanceRecord[start], start))\n",
    "        while priority_queue.qsize() > 0:\n",
    "            dis, cur_node = priority_queue.get()\n",
    "            if cur_node == end:\n",
    "                return 0 - dis\n",
    "\n",
    "            if dis > distanceRecord[cur_node]:\n",
    "                continue\n",
    "\n",
    "            for i, new_node in enumerate(graph[cur_node]):\n",
    "                new_weight = weight[cur_node][i] * dis\n",
    "                if new_weight < distanceRecord[new_node]:\n",
    "                    distanceRecord[new_node] = new_weight\n",
    "                    priority_queue.put((new_weight, new_node))\n",
    "\n",
    "        return 0.\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[start] = 1\n",
    "        while True:\n",
    "            k = True\n",
    "            for j in range(len(edges)):\n",
    "                if dp[edges[j][0]]*succProb[j]>dp[edges[j][1]]:\n",
    "                    dp[edges[j][1]] = dp[edges[j][0]]*succProb[j]\n",
    "                    k = False\n",
    "                if dp[edges[j][1]]*succProb[j]>dp[edges[j][0]]:\n",
    "                    dp[edges[j][0]] = dp[edges[j][1]]*succProb[j]\n",
    "                    k = False\n",
    "            if k: break\n",
    "        return dp[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        graph, q, p = [{} for _ in range(n)], [start], [0] * n\n",
    "        p[start] = 1\n",
    "        for (u, v), k in zip(edges, succProb):\n",
    "            graph[u][v] = graph[v][u] = k\n",
    "        for i in q:\n",
    "            for j in graph[i]:\n",
    "                if (cur := p[i] * graph[i][j]) > p[j]:\n",
    "                    q.append(j)\n",
    "                    p[j] = cur\n",
    "        return p[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        import queue\n",
    "        graph, weights = self.build_graph(n, edges, succProb)\n",
    "        dists = [0] * n\n",
    "        que = queue.PriorityQueue()\n",
    "        que.put((-1, start))\n",
    "        while que.qsize() > 0:\n",
    "            node = que.get()\n",
    "            node_id = node[1]\n",
    "            node_dist = -node[0]\n",
    "            if node_id == end:\n",
    "                return node_dist\n",
    "            if node_dist < dists[node_id]:\n",
    "                continue\n",
    "            for adj,w in zip(graph[node_id],weights[node_id]):\n",
    "                d = node_dist * w\n",
    "                if d > dists[adj]:\n",
    "                    que.put((-d,adj))\n",
    "                    dists[adj] = d\n",
    "                \n",
    "        return dists[end]\n",
    "    def build_graph(self, n, edges, probs):\n",
    "        graph = [[] for _ in range(n)]\n",
    "        weights = [[] for _ in range(n)]\n",
    "        for edge,prob in zip(edges, probs):\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "            weights[edge[0]].append(prob)\n",
    "            weights[edge[1]].append(prob)\n",
    "        return graph, weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        e=[[]*n for _ in range(n)]\n",
    "        for i,(a,b) in enumerate(edges):\n",
    "            e[a].append((b,succProb[i]))\n",
    "            e[b].append((a,succProb[i]))\n",
    "        def spfa(edges, n, start):\n",
    "            dis = [0] * n\n",
    "            dis[start], vis, cnt = 1, [0] * n, [0] * n\n",
    "            q, vis[start] = collections.deque([start]), 1\n",
    "            while q:\n",
    "                cur, vis[cur] = q.popleft(), 0\n",
    "                for nxt, weight in edges[cur]:\n",
    "                    if dis[nxt] < dis[cur] * weight:\n",
    "                        dis[nxt] = dis[cur] * weight\n",
    "                        cnt[nxt] = cnt[cur] + 1\n",
    "                        if cnt[nxt] > n:\n",
    "                            return -1\n",
    "                        if vis[nxt] == 0:\n",
    "                            q.append(nxt)\n",
    "                            vis[nxt] = 1\n",
    "            return dis\n",
    "        return spfa(e,n+1,start)[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        graph, q, p = [{} for _ in range(n)], [start], [0] * n\n",
    "        p[start] = 1\n",
    "        for (u, v), k in zip(edges, succProb):\n",
    "            graph[u][v] = graph[v][u] = k\n",
    "        for i in q:\n",
    "            for j in graph[i]:\n",
    "                if (cur := p[i] * graph[i][j]) > p[j]:\n",
    "                    q.append(j)\n",
    "                    p[j] = cur\n",
    "        return p[end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        m = len(edges)\n",
    "        graph = defaultdict(list)\n",
    "        for i, [a, b] in enumerate(edges):\n",
    "            graph[a].append(i) \n",
    "            graph[b].append(i)\n",
    "        \n",
    "        dist = [0] * n\n",
    "        def djkstra(s, dist):\n",
    "            visited = [0] * n \n",
    "            dist[s] = 1 \n",
    "            Q = [(-1,s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if visited[u]:\n",
    "                    continue\n",
    "                visited[u] = 1 \n",
    "                for ei in graph[u]:\n",
    "                    v = edges[ei][0] if edges[ei][0] != u else edges[ei][1]\n",
    "                    if dist[v] < dist[u] * succProb[ei]:\n",
    "                        dist[v] = dist[u] * succProb[ei] \n",
    "                        heapq.heappush(Q, (-dist[v], v))\n",
    "\n",
    "        djkstra(start_node, dist) \n",
    "        return dist[end_node] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        # \"\"\"朴素地杰斯特拉（权重不为加，而是相乘）\"\"\"\n",
    "        # # 建图\n",
    "        # graph = collections.defaultdict(list)\n",
    "        # for i, (x, y) in enumerate(edges):\n",
    "        #     graph[x].append((succProb[i], y))\n",
    "        #     graph[y].append((succProb[i], x))\n",
    "        \n",
    "        # que = [(-1.0, start)]\n",
    "        # prob = [0.0] * n        # 表示dist\n",
    "        # prob[start] = 1.0\n",
    "\n",
    "        # while que:\n",
    "        #     pr, node = heapq.heappop(que)\n",
    "        #     pr = -pr\n",
    "        #     if pr < prob[node]:\n",
    "        #         continue\n",
    "        #     for prNext, nodeNext in graph[node]:\n",
    "        #         if prob[nodeNext] < prob[node] * prNext:\n",
    "        #             prob[nodeNext] = prob[node] * prNext\n",
    "        #             heapq.heappush(que, (-prob[nodeNext], nodeNext))\n",
    "        \n",
    "        # return prob[end]\n",
    "\n",
    "        \"\"\"\"堆优化地杰斯特拉\"\"\"\n",
    "        g = collections.defaultdict(list)\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            g[x].append((y, succProb[i]))\n",
    "            g[y].append((x, succProb[i]))\n",
    "\n",
    "        dist = [0.0] * n\n",
    "        dist[start] = 1.0\n",
    "        q = [(0, start)]\n",
    "        while q:\n",
    "            time, x = heapq.heappop(q)\n",
    "            time = -time        # 这里是和最短距离反过来的体现，表示最大概率\n",
    "            if dist[x] < time:\n",
    "                continue\n",
    "            for y, time in g[x]:\n",
    "                if (d := dist[x] * time) > dist[y]:     # + 变 *, < 变 >\n",
    "                    dist[y] = d\n",
    "                    heapq.heappush(q, (-d, y))      # d前面加-\n",
    "\n",
    "        return dist[end]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        p = [0] * n\n",
    "        p[start_node] = 1\n",
    "\n",
    "        while True:\n",
    "            f = p.copy()\n",
    "            change = False\n",
    "            for i, edge in enumerate(edges):\n",
    "                a, b = edge\n",
    "                if p[b] < p[a] * succProb[i]:\n",
    "                    p[b] = p[a] * succProb[i]\n",
    "                    change = True\n",
    "                if p[a] < p[b]*succProb[i]:\n",
    "                    p[a] = p[b]*succProb[i]\n",
    "                    change = True\n",
    "            \n",
    "            if not change: break\n",
    "        return p[end_node]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:      \n",
    "        dct = defaultdict(dict)\n",
    "        m = len(edges)\n",
    "        dist = [0]*(n+1)\n",
    "        dist[start_node] = -1\n",
    "        stack = []\n",
    "        for i in range(m):\n",
    "            u=edges[i][0]\n",
    "            v=edges[i][1]\n",
    "            dct[u][v] = succProb[i] #\n",
    "            dct[v][u] = succProb[i]\n",
    "        heappush(stack,[dist[start_node],start_node]) \n",
    "        while stack: # \n",
    "            d,i = heappop(stack)\n",
    "            if d > dist[i]:\n",
    "                continue\n",
    "            for j in dct[i]:\n",
    "                if d*dct[i][j] < dist[j]:\n",
    "                    dist[j] = d*dct[i][j]\n",
    "                    heappush(stack,[dist[j],j]) #进入heap用负值（小顶堆）\n",
    "        return abs(dist[end_node]) if dist[end_node] != 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        graph = [{} for _ in range(n)]\n",
    "        for i, edge in enumerate(edges):\n",
    "            graph[edge[0]][edge[1]] = succProb[i]\n",
    "            graph[edge[1]][edge[0]] = succProb[i]\n",
    "        distance = [0] * n\n",
    "        distance[start_node] = 1\n",
    "        q = {start_node}\n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            for neighbor, neighbor_prob in graph[node].items():\n",
    "                if distance[node] * neighbor_prob > distance[neighbor]:\n",
    "                    distance[neighbor] = distance[node] * neighbor_prob\n",
    "                    q.add(neighbor)\n",
    "        return distance[end_node]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        # 构造节点邻接表,格式为{起点：[(终点,概率)]}\n",
    "        from collections import defaultdict\n",
    "        st_maps = defaultdict(list)\n",
    "        for i, (s, e) in enumerate(edges):\n",
    "            st_maps[s].append((e, succProb[i]))\n",
    "            st_maps[e].append((s, succProb[i]))\n",
    "        ans = 0\n",
    "        queue = deque([(start,1)])\n",
    "        visited = {start:0}\n",
    "\n",
    "        while queue:\n",
    "            cur_node,cur_pro = queue.popleft()\n",
    "            for next_node ,pro in st_maps[cur_node]:\n",
    "\n",
    "                next_pro = pro*cur_pro \n",
    "                \n",
    "                if next_node == end:\n",
    "                    ans = max(ans,next_pro)\n",
    "                    continue \n",
    "                \n",
    "                if next_pro > ans and (next_node not in visited or visited[next_node]<next_pro):\n",
    "                    queue.append((next_node,next_pro))\n",
    "                    visited[next_node]=next_pro \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            graph[x].append((succProb[i], y))\n",
    "            graph[y].append((succProb[i], x))\n",
    "        \n",
    "        que = [(-1.0, start)]\n",
    "        prob = [0.0] * n\n",
    "        prob[start] = 1.0\n",
    "\n",
    "        while que:\n",
    "            pr, node = heapq.heappop(que)\n",
    "            pr = -pr\n",
    "            if pr < prob[node]:\n",
    "                continue\n",
    "            for prNext, nodeNext in graph[node]:\n",
    "                if prob[nodeNext] < prob[node] * prNext:\n",
    "                    prob[nodeNext] = prob[node] * prNext\n",
    "                    heapq.heappush(que, (-prob[nodeNext], nodeNext))\n",
    "        \n",
    "        return prob[end]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            graph[x].append((succProb[i], y))\n",
    "            graph[y].append((succProb[i], x))       \n",
    "        que = []\n",
    "        heapq.heappush(que, (-1.0, start))\n",
    "        prob = [0.0] * n\n",
    "        prob[start] = 1.0\n",
    "        while que:\n",
    "            pr, node = heapq.heappop(que)\n",
    "            pr = -pr\n",
    "            if node == end:\n",
    "                return pr\n",
    "            if pr < prob[node]:\n",
    "                continue\n",
    "            for prNext, nodeNext in graph[node]:\n",
    "                if prob[nodeNext] < prob[node] * prNext:\n",
    "                    prob[nodeNext] = prob[node] * prNext\n",
    "                    heapq.heappush(que, (-prob[nodeNext], nodeNext))       \n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            n1, n2 = edges[i]\n",
    "            p = succProb[i]\n",
    "            graph[n1].append([n2, p])\n",
    "            graph[n2].append([n1, p])\n",
    "        \n",
    "        pq = []\n",
    "\n",
    "        distTo = [0] * n\n",
    "        distTo[start_node] = 1\n",
    "\n",
    "        heapq.heappush(pq, [-1, start_node])\n",
    "\n",
    "        while pq:\n",
    "            neg_prob, node = heapq.heappop(pq)\n",
    "            prob = -neg_prob\n",
    "            if prob < distTo[node]:\n",
    "                continue\n",
    "            \n",
    "            for edge in graph[node]:\n",
    "                c_n, c_p = edge\n",
    "                new_p = c_p * prob\n",
    "                if new_p > distTo[c_n]:\n",
    "                    distTo[c_n] = new_p\n",
    "                    heapq.heappush(pq, [-new_p, c_n])\n",
    "        \n",
    "        return distTo[end_node]\n",
    "\n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "\n",
    "class NodeState:\n",
    "    def __init__(self, id, distance):\n",
    "        self.id = id\n",
    "        self.dis_from_start = distance\n",
    "\n",
    "    def __lt__(self, state):\n",
    "        return  self.dis_from_start > state.dis_from_start\n",
    "\n",
    "def dijkstra(graph, start, end):\n",
    "    num_node = len(graph)\n",
    "    dst_from_start = [-1. for _ in range(num_node)]\n",
    "    dst_from_start[start] = 1.\n",
    "\n",
    "    state_que = PriorityQueue()\n",
    "    state_que.put(NodeState(start, 1.))\n",
    "\n",
    "    while not state_que.empty():\n",
    "        state_node = state_que.get()\n",
    "        node_id = state_node.id\n",
    "        if dst_from_start[node_id] > state_node.dis_from_start:\n",
    "            continue\n",
    "\n",
    "        for neighbour in graph[node_id]:\n",
    "            next_id = neighbour[0]\n",
    "            weight = neighbour[1]\n",
    "            if dst_from_start[next_id] < state_node.dis_from_start * weight:\n",
    "                dst_from_start[next_id] = state_node.dis_from_start * weight\n",
    "                state_que.put(NodeState(next_id, dst_from_start[next_id]))\n",
    "    return 0.0 if dst_from_start[end] < 0 else dst_from_start[end]\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for idx, edge in enumerate(edges):\n",
    "            s, e = edge\n",
    "            prob = succProb[idx]\n",
    "            graph[s].append((e, prob))\n",
    "            graph[e].append((s, prob))\n",
    "        return dijkstra(graph, start_node, end_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        g = defaultdict(list)\n",
    "        for (a, b), p in zip(edges, succProb):\n",
    "            g[a].append((b, -log(p)))\n",
    "            g[b].append((a, -log(p)))\n",
    "        f = [float(\"inf\") for _ in range(n)]\n",
    "        f[start_node] = 0.\n",
    "        h, seen = [(0., start_node)], set()\n",
    "        while h:\n",
    "            nlp_u, u = heappop(h)\n",
    "            if nlp_u > f[u]: continue\n",
    "            seen.add(u)\n",
    "            for v, nlp_v in g[u]:\n",
    "                if v not in seen and nlp_u + nlp_v < f[v]:\n",
    "                    f[v] = nlp_u + nlp_v\n",
    "                    heappush(h, (f[v], v))\n",
    "        return exp(-f[end_node])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for (x, y), p in zip(edges, succProb):\n",
    "            graph[x].append([y, p])\n",
    "            graph[y].append([x, p]) # this line since undirected\n",
    "        heap = []\n",
    "        heapq.heappush(heap, [-1, start])\n",
    "        dist = collections.defaultdict(int)\n",
    "        while heap:\n",
    "            prob, node = heapq.heappop(heap) # node, p wrong\n",
    "            prob = -prob # very important \n",
    "            if node == end:\n",
    "                return prob\n",
    "            if node in dist:\n",
    "                continue\n",
    "            dist[node] = prob\n",
    "            for nei, p in graph[node]: # wrong dist:\n",
    "                # heapq.heappush(heap, [nei, np * p]) VERY wrong. np* p must bevfirst\n",
    "                heapq.heappush(heap, [-prob*p, nei]) # -\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:\n",
    "        import heapq\n",
    "\n",
    "        def dijkstra(graph, start, end):\n",
    "            # 初始化距离字典，存储从起点到每个节点的距离\n",
    "            distances = {node: 1 for node in graph}\n",
    "            distances[start] = -1\n",
    "\n",
    "            # 初始化路径字典，用于回溯路径\n",
    "            paths = {node: [] for node in graph}\n",
    "\n",
    "            # 用于存储已访问的节点\n",
    "            visited = set()\n",
    "\n",
    "            # 优先队列，用于选择下一个要访问的节点\n",
    "            priority_queue = [(-1, start)]\n",
    "\n",
    "            while priority_queue:\n",
    "                current_distance, current_node = heapq.heappop(priority_queue)\n",
    "\n",
    "                if current_node in visited:\n",
    "                    continue\n",
    "\n",
    "                visited.add(current_node)\n",
    "\n",
    "                for neighbor, weight in graph[current_node].items():\n",
    "                    distance = current_distance * weight\n",
    "\n",
    "                    if distance < distances[neighbor]:\n",
    "                        distances[neighbor] = distance\n",
    "                        paths[neighbor] = [node for node in paths[current_node]] + [current_node]\n",
    "                        heapq.heappush(priority_queue, (distance, neighbor))\n",
    "\n",
    "            if distances[end] == float('inf'):\n",
    "                return \"无法到达目标节点\"\n",
    "\n",
    "            print(distances)\n",
    "\n",
    "            # 查找所有具有相同最短路径长度的路径\n",
    "            shortest_paths = []\n",
    "            min_distance = distances[end]\n",
    "            print(\"min_distance: \", -min_distance)\n",
    "\n",
    "            # def find_paths(node, path):\n",
    "            #     if node == end:\n",
    "            #         shortest_paths.append(path)\n",
    "            #         return\n",
    "            #     for neighbor in graph[node]:\n",
    "            #         if distances[neighbor] == distances[node] + graph[node][neighbor]:\n",
    "            #             find_paths(neighbor, path + [neighbor])\n",
    "\n",
    "            # find_paths(start, [start])\n",
    "\n",
    "            \n",
    "\n",
    "            return min_distance, shortest_paths\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        matrix = defaultdict(dict)\n",
    "        for i in range(n):\n",
    "            matrix[i][i] = 1\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            matrix[edges[i][0]][edges[i][1]] = succProb[i]\n",
    "            matrix[edges[i][1]][edges[i][0]] = succProb[i]\n",
    "\n",
    "        # print(matrix)\n",
    "        min_distance, shortest_paths = dijkstra(matrix, start_node, end_node)\n",
    "        # print(shortest_paths)\n",
    "\n",
    "        \n",
    "        return max(-min_distance, 0)\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
